import heapq
from collections import Counter
from typing import List
class Solution:
    """
    方法：使用最小堆维护前k个最频繁元素
    
    Args:
        nums: List[int], 输入数组
        k: int, 需要返回的最频繁元素的数量
        
    Returns:
        List[int]: 前k个最频繁元素的列表
        
    Time: O(nlogk), 其中n是数组长度，每次堆操作需要O(logk)时间
    Space: O(n), 需要存储所有元素的频率
    """
    def topKFrequent(self, nums: List[int], k: int) -> List[int]:
        count = Counter(nums)
        # 使用最小堆维护前k大元素 O(n logk)
        heap = []
        for num, freq in count.items():
            if len(heap) < k:
                heapq.heappush(heap, (freq, num))
            else:
                if freq > heap[0][0]:
                    heapq.heappop(heap)
                    heapq.heappush(heap, (freq, num))
        return [num for freq, num in heap]

    """
    方法：桶排序法
    使用桶排序的思想，将相同频率的元素放入同一个桶中，然后从高频率桶开始收集元素，直到收集到k个元素为止。
    
    Args:
        nums: List[int], 输入数组
        k: int, 需要返回的最频繁元素的数量
        
    Returns:
        List[int]: 前k个最频繁元素的列表
        
    Time: O(n), 其中n是数组长度，统计频率O(n)，构建桶O(n)，收集结果O(k)
    Space: O(n), 需要存储所有元素的频率和桶
    """
    def topKFrequent1(self, nums: List[int], k: int) -> List[int]:
        # 第一步：统计每个元素的出现次数
        cnt = Counter(nums)
        max_cnt = max(cnt.values())
        # 第二步：把出现次数相同的元素，放到同一个桶中
        buckets = [[] for _ in range(max_cnt +1)]
        for x, c in cnt.items():
            buckets[c].append(x)
        # 第三步：倒序遍历 buckets，把出现次数前 k 大的元素加入答案
        ans = []
        for bucket in reversed(buckets):
            ans += bucket
            if len(ans) == k:
                return ans

